CODE 2. Palindrome Partitioning

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/16/2013-09-16-CODE 2 Palindrome Partitioning/

访问原文「CODE 2. Palindrome Partitioning」

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
[“aa”,”b”],
[“a”,”a”,”b”]
]

public ArrayList<ArrayList<String>> partition(String s) {
	if (s == null || s.length() == 0)
		return new ArrayList<ArrayList<String>>();
	boolean[][] isPalindromes = new boolean[s.length()][s.length()];
	int[] pa = new int[s.length()];
	for (int i = 0; i < s.length(); i++) {
		isPalindromes[i][i] = true;
		pa[i] = 0;
	}
	for (int i = s.length() - 2; i >= 0; i--) {
		isPalindromes[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
		for (int j = i + 2; j < s.length(); j++)
			isPalindromes[i][j] = (s.charAt(i) == s.charAt(j))
					&& isPalindromes[i + 1][j - 1];
	}
	return getPalindromes(s, isPalindromes, 0);
}

private ArrayList<ArrayList<String>> getPalindromes(String s,
		boolean[][] isPalindromes, int start) {
	ArrayList<ArrayList<String>> results = new ArrayList<ArrayList<String>>();
	if (start > s.length() - 1) {
		results.add(new ArrayList<String>());
		return results;
	}
	for (int i = start; i < s.length(); i++) {
		if (isPalindromes[start][i]) {
			for (ArrayList<String> subPa : getPalindromes(s, isPalindromes,
					i + 1)) {
				subPa.add(0, s.substring(start, i + 1));
				results.add(subPa);
			}

		}
	}
	return results;
}